package com.lht.leetcodeDemo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Eric
 * @version 1.0
 * @date 2019-12-11
 */
public class MergeIntervals {
    public static void main(String[] args) {
//        int[][] a = new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}};
//        int[][] a = new int[][]{{1, 4}, {4, 5}};
//        int[][] a = new int[][] {{1,4},{0,4}};
//        int[][] a = new int[][]{{1, 4}, {0, 0}};
        int[][] a = new int[][] {{2,3},{4,5},{6,7},{8,9},{1,10}};
        int[][] arr = new MergeIntervals().merge(a);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(Arrays.toString(arr[i]));
        }
    }

    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length < 2) {
            return intervals;
        }
        // 排序
        for (int i = 0; i < intervals.length; i++) {
            for (int j = i + 1; j < intervals.length; j++) {
                if (intervals[i][0] > intervals[j][0]) {
                    int[] tmp = intervals[i];
                    intervals[i] = intervals[j];
                    intervals[j] = tmp;
                }
            }
        }

        List<int[]> arr = new ArrayList<>();

        int i = 0;
        int[] f = intervals[i];
        // 如果最后一个都被合并了，则不用考虑了
        while (i + 1 < intervals.length) {
            int[] s = intervals[i + 1];
            if (f[1] >= s[0]) {
                if (f[0] > s[1]) {
                    // s 区间比 f 小
                    arr.add(s);
                } else {
                    f[0] = s[0] < f[0] ? s[0] : f[0];
                    f[1] = f[1] < s[1] ? s[1] : f[1];
                }
            } else {
                arr.add(f);
                f = s;
            }
            i++;
        }
        // 最后一个 肯定要保存
        arr.add(f);

        int[][] rst = new int[arr.size()][2];
        for (int j = 0; j < arr.size(); j++) {
            rst[j] = arr.get(j);
        }
        return rst;
    }
}
